|
In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It is an alternative to lock-based synchronization. STM is a strategy implemented in software, rather than as a hardware component. A transaction in this context occurs when a piece of code executes a series of reads and writes to shared memory. These reads and writes logically occur at a single instant in time; intermediate states are not visible to other (successful) transactions. The idea of providing hardware support for transactions originated in a 1986 paper by Tom Knight.〔Tom Knight. ''(An architecture for mostly functional languages. )'' Proceedings of the 1986 ACM conference on LISP and functional programming.〕 The idea was popularized by Maurice Herlihy and J. Eliot B. Moss.〔Maurice Herlihy and J. Eliot B. Moss. ''Transactional memory: architectural support for lock-free data structures.'' Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.〕 In 1995 Nir Shavit and Dan Touitou extended this idea to software-only transactional memory (STM).〔Nir Shavit and Dan Touitou. ''Software transactional memory.'' Distributed Computing. Volume 10, Number 2. February 1997.〕 Since 2005, STM has been the focus of intense research〔(【引用サイトリンク】url=http://scholar.google.com/scholar?as_ylo=2005&q=%22software+transactional+memory%22 )〕 and support for practical implementations is growing. == Performance == Unlike the locking techniques used in most modern multithreaded applications, STM is very optimistic: a thread completes modifications to shared memory without regard for what other threads might be doing, recording every read and write that it is performing in a log. Instead of placing the onus on the writer to make sure it does not adversely affect other operations in progress, it is placed on the reader, who after completing an entire transaction verifies that other threads have not concurrently made changes to memory that it accessed in the past. This final operation, in which the changes of a transaction are validated and, if validation is successful, made permanent, is called a ''commit''. A transaction may also ''abort'' at any time, causing all of its prior changes to be rolled back or undone. If a transaction cannot be committed due to conflicting changes, it is typically aborted and re-executed from the beginning until it succeeds. The benefit of this optimistic approach is increased concurrency: no thread needs to wait for access to a resource, and different threads can safely and simultaneously modify disjoint parts of a data structure that would normally be protected under the same lock. However, in practice STM systems also suffer a performance hit compared to fine-grained lock-based systems on small numbers of processors (1 to 4 depending on the application). This is due primarily to the overhead associated with maintaining the log and the time spent committing transactions. Even in this case performance is typically no worse than twice as slow. Advocates of STM believe this penalty is justified by the conceptual benefits of STM. Theoretically, the worst case space and time complexity of ''n'' concurrent transactions is ''O''(''n''). Actual needs depend on implementation details (one can make transactions fail early enough to avoid overhead), but there will also be cases, albeit rare, where lock-based algorithms have better time complexity than software transactional memory. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Software transactional memory」の詳細全文を読む スポンサード リンク
|